

import java.awt.Point;
import java.awt.Rectangle;
import java.awt.geom.Rectangle2D;

/**
 * Clip a line segment against a rectangular area
 * @author Avshalom Elmalech 	039281167
 * @author Moshe 	Beutel 		037580792
 */
public class Clipper {
	
	/**
	 * Clip a line against a rectangle. 
	 * @param pIn1 - First vertex of edge before clipping.
	 * @param pIn2 - Second vertex of edge before clipping.
	 * @param rect - Rectangular area that line segment is clipped against.
	 * @return start and end point of the intersected segment. null if segment is outside.
	 */
	public static Pair<Point> ClipLine(Point pIn1, Point pIn2, Rectangle rect){
		Pair<Point> clippedPoints;
		int outcode1 = GenerateOutCode(pIn1, rect);
		int outcode2 = GenerateOutCode(pIn2, rect);
		int outcode  = outcode1 & outcode2;
		if(outcode1 == 0 && outcode2 == 0){
			// both points inside rectangle (and so is the whole segment) - keep both
			clippedPoints =  new Pair<Point>(pIn1, pIn2);
		}else if(outcode != 0){
			// both points are left \ right \ up \ down the rectangle (and so is the whole segment) - throw both
			clippedPoints =  null;
		}else if(outcode1 == 0){
			// pIn1 inside - keep it and search for intersection point with rectangle
			assert outcode2 != 0;
			clippedPoints =  new Pair<Point>(pIn1, SearchForExit(pIn1, pIn2, rect));
		}else if (outcode2 == 0) {
			// pIn2 inside - keep it and search for intersection point with rectangle
			assert outcode1 != 0;
			clippedPoints = new Pair<Point>(pIn2, SearchForExit(pIn2, pIn1, rect));
		}else {
			// both points outside - 2 points of intersection or none
			clippedPoints = SegmentRectIntersect(pIn1, pIn2, rect);
		}
			
		if(clippedPoints != null && (clippedPoints.value1 == null || clippedPoints.value2 == null))
			clippedPoints = null;  // return 2 point2 or none
		
		return clippedPoints;
		
	}
	
	/**
	 * This method is used for Cohen - Sutherlend's general case.
	 * Segments ends are both outside the rectangle but its not clear if there are 2 points 
	 * of intersection or none (intersection at s vertex is not interesting because there is no line to paint).
	 * @param p1
	 * @param p2
	 * @param rect
	 * @return
	 */
	private static Pair<Point> SegmentRectIntersect(Point p1, Point p2, Rectangle rect){
		Point[] outs = new Point[2];
		int intersections = 0;
		Pair<Point> rightLeft =  SortPointsRightLeft(p1, p2);
		Pair<Point> upDown =  SortPointsUpDown(p1, p2);
		
		if (upDown.value1.y < rect.y   ) 
			outs[intersections] = IntersectHorizontalEdge(upDown.value1, upDown.value2, rect.x, rect.x + rect.width, rect.y, 0);
		
		if (outs[intersections] != null) 
			++intersections;
		
		if (upDown.value2.y > rect.y + rect.height)
			outs[intersections] = IntersectHorizontalEdge(upDown.value1, upDown.value2, rect.x, rect.x + rect.width, rect.y + rect.height, 0);
		
		if (outs[intersections] != null) 
			++intersections;
		
		if(intersections < 2){
			if (rightLeft.value1.x > rect.x + rect.width ) 	
			outs[intersections] = IntersectVerticallEdge(rightLeft.value2, rightLeft.value1, rect.y, rect.y + rect.height, rect.x + rect.width, 0);
		
			if (outs[intersections] != null) 
				++intersections;
		
			if (intersections < 2 && rightLeft.value2.x < rect.x) 
				outs[intersections] = IntersectVerticallEdge(rightLeft.value2, rightLeft.value1, rect.y, rect.y + rect.height,  rect.x, 0);
		}
		
		if(intersections == 0)  // no intersection
			return null;
		
		// double intersection
		return new Pair<Point>(outs[0], outs[1]);
	}
	
	/**
	 * Search for an intersection point between the inside segment point - outside segment point and rectangle.
	 * @param inside - A point inside rectangle
	 * @param outside - A point outside rectangle.
	 * @param rect - The rectangle 
	 * @return Intersection point.
	 */
	private static Point SearchForExit(Point inside, Point outside, Rectangle rect){
		Point p = null;
		if(outside.y > rect.y + rect.height) // exit down
			p = IntersectHorizontalEdge(inside, outside, rect.x, rect.x + rect.width, rect.y + rect.height, 0);
		if (p == null && outside.x > rect.x + rect.width) // exit right
			p = IntersectVerticallEdge(inside, outside, rect.y, rect.y + rect.height, rect.x + rect.width, 0);
		if(p == null && outside.y < rect.y)  // exit up
			p = IntersectHorizontalEdge(inside, outside, rect.x, rect.x + rect.width, rect.y, 0 );
		if(p == null)	// exit left
			p = IntersectVerticallEdge(inside, outside, rect.y, rect.y + rect.height, rect.x, 0 );
		
		return p;
	}
	
	/**
	 * Generates Cohen - Sutherland vertex code which determines its relative position w.r.t the rectangle
	 * @param p
	 * @param rect
	 * @return outcode
	 */
	private static int GenerateOutCode(Point p, Rectangle rect){
		int res = 0;
		
		if(p.x < rect.x)
			res |= Rectangle2D.OUT_LEFT;
		else if (p.x > rect.x + rect.width) 
			res |= Rectangle2D.OUT_RIGHT;
		
		if (p.y < rect.y) 
			res |= Rectangle2D.OUT_TOP;
		else if (p.y > rect.y + rect.height) 
			res |= Rectangle2D.OUT_BOTTOM;
		
		return res;
	}
	
	/**
	 * Calculate intersection point between a line segment and a rectangle vertical edge.
	 * @param firstStart
	 * @param firstEnd
	 * @param verticalStartY
	 * @param verticalEndY
	 * @param verticalX
	 * @return point of intersection
	 */
	private static Point IntersectVerticallEdge(Point firstStart, Point firstEnd, int verticalStartY, int verticalEndY, int verticalX, int depth){	
	
		if(depth == 10) return null;
		
		Point p  = FindMidPoint(firstStart, firstEnd);
		
		if (p.x == verticalX) {
			assert verticalEndY > verticalStartY;
			if (p.y >= verticalStartY && p.y <= verticalEndY) 
				return p;
			else 
				return null;
			
		}else{
			if(firstEnd.x == firstStart.x)
				return null;
			Point s = null, e = null;
			Pair<Point> pair  =  SortPointsRightLeft(firstStart, firstEnd);
			if (p.x > verticalX) {
				s = p;
				e = pair.value2;
			}else{
				s = pair.value1;
				e = p;
			}
			
			return IntersectVerticallEdge(s, e, verticalStartY, verticalEndY, verticalX, ++depth);
		}
	}
	
	
	/**
	 * Calculate intersection point between line segments.
	 * @param firstStart - first segment start point.
	 * @param firstEnd - first segment end point.
	 * @param horizontarStartX - horizontal edge lowest x coordinate.
	 * @param horizontalEndX - horizontal edge highest x coordinate.
	 * @param horizontalY - y coordinate of horizontal edge.
	 * @return
	 */
	private static Point IntersectHorizontalEdge(Point firstStart, Point firstEnd, int horizontarStartX, int horizontalEndX, int horizontalY, int depth){	
		if(depth == 10) return null;
		
		Point p  = FindMidPoint(firstStart, firstEnd);
		
		if (p.y == horizontalY) {
			assert horizontalEndX > horizontarStartX;
			if (p.x >= horizontarStartX && p.x <= horizontalEndX) 
				return p;
			else 
				return null;
		}else{
			if(firstEnd.y == firstStart.y)
							return null;
			Point s = null, e = null;
			Pair<Point> pair = SortPointsUpDown(firstStart, firstEnd);
			if (p.y < horizontalY) {
				s = p;
				e = pair.value2;
			}else{
				s = pair.value1;
				e = p;
			}
			return IntersectHorizontalEdge(s, e, horizontarStartX, horizontalEndX, horizontalY, ++depth);
		}			
	}
	
	/**
	 * Get 2 points and find their midpoint.
	 * @param p1 - first point.
	 * @param p2 - second point.
	 * @return - calculated midpoint.
	 */
	private static Point FindMidPoint(Point p1, Point p2) {
		int x = (p1.x + p2.x) / 2;
		int y = (p1.y + p2.y) / 2;
		return new Point(x,y);
	}
	
	/**
	 * Determines which point is higher (smaller y value)
	 * @param p1 - input point
	 * @param p2 - input point
	 * @return A pair of points in which value1 point is higher than value2 point 
	 */
	private static Pair<Point> SortPointsUpDown(Point p1, Point p2) {
		if (p1.y < p2.y) {
			return new Pair<Point>(p1,p2);
		}else {
			return new Pair<Point>(p2,p1);
		}
	}
	
	/**
	 * Determines which point is on the right (higher x value)
	 * @param p1 - input point
	 * @param p2 - input point
	 * @return A pair of points in which value1 point is on the right of value2 point 
	 */
	private static Pair<Point> SortPointsRightLeft(Point p1, Point p2) {
		if (p1.x > p2.x) {
			return new Pair<Point>(p1,p2);
		}else {
			return new Pair<Point>(p2,p1);
		}
	}
	
}
